不妨设 , 且$ n < m $。

回忆一下卡塔兰数的推导过程 , 我们用类似的方法解决此题。
An Ac a day, keeps the doctor away!
显然,在一个强联通分量中,只要有一个城市与s联通,那么整个分量就与s联通。
于是我们可以缩点,统计它的入度。如果入度为0,我们就从s向这个缩点连一条边,如果入度不为0,说明其他城市可以到达它,我们就不需要单独连边。
最后,注意特判与s在同一强联通分量的点。
i=1∑nj=1∑mlcm(i,j)
首先,我们得知道过原点与两点的抛物线解析式:
设该函数解析式为 y=ax2+bx+c(a<0)且过 (0,0),(x1,y1),(x2,y2) 三点。
由函数过 (0,0) 得 c=0。
对于每个位置 i , 我们向 pi 连一条边。 结合题意可知,一个合法的排列,是一个由 n 个自环组成的图。
但现在会形成多个环,不妨记环的数量为 k , 第 i 个环的大小为 si(包括自环)。
我们现在要做的,就是将这 k 个环拆成 n 个自环。
这道题用后缀自动机可以暴力解决。
建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 , 我们就可以在 DAWG 上 dp 。 dp[u]表示包含转移u的子串数量,很容易列出转移式:
一道后缀自动机的板题。
我们从根结点开始匹配,如果有转移就将cnt++
不然就顺着后缀链接向上跳,直到找到有转移的点,用 Maxlen 继续匹配。(后缀链接一定是它的子串,也能被匹配)。